Plus ou moins entretenu selon les époques, le parc fut, comme le palais, réaménagé lors des chantiers du milieu du XVIIIe siècle : on y installa des bassins, des fontaines, l’eau de la Selle voisine étant amenée dans des canalisations de bois et de plomb. Il se dit, depuis longtemps, que le parc fut dessiné par Lenôtre, l’architecte du parc de Versailles (une célébrité en son temps). Aucun document ne peut à ce jour en attester. À la Révolution, on fait table rase du passé : comme dans toute la France, les bâtiments religieux sont vendus comme biens nationaux. En 1794, « le Palais avec tous ses bâtiments, jardins et promenades en dépendant, occupés ci-devant par l’Archevêque de Cambrai » échoient à un citoyen parisien pour la somme de 58 200 francs. 

Malgré les réaménagements successifs du XIXe et du XXe siècle, l’implantation des tissages et filatures à partir des années 1806-1813, le parc est protégé. Racheté par la ville du Cateau, remis en état, il est ouvert au public à partir de 1884. Le buste de Fénelon, commande de l’Etat à Séraphin Sénécheau (formé dans les ateliers de Rude et David d’Angers) est installé sur une terrasse. Beaucoup doutent qu’il s’agisse de Fénelon : plutôt son successeur, monseigneur de Choiseul. Une fontaine est posée à proximité sur la place Thiers – les Catésiens l’appellent le Jet d’eau ; une serre est mise en place au bord de la Selle toute proche. Tout cela apportant un peu de verdure et de fraîcheur dans une ville désormais toute entière dévolue à l’industrie textile.

Pendant l’occupation de la Grande Guerre, les Allemands investirent le parc pour de martiales parades dont ils avaient le secret, exhibant sur la terrasse d’imposantes pièces d’artillerie, une fois les leurs, une autre fois celles prises aux Anglais lors de la bataille de Cambrai en 1917. A la libération, les Britanniques l’investirent à leur tour pour les troupes de passage. Nettoyé de ces cinq années souvent peu respectueuses, le parc du palais Fénelon fut une fois encore rénové par des architectes paysagistes. Revenus en 1940, les Allemands y firent, semble-t-il, moins de dégâts : un récit rapporte que peu avant la Libération, lors d’une visite de l’architecte en chef des monuments historiques, l’officier allemand responsable du site expliqua qu’il s’était arrangé pour ne pas y faire creuser des tranchées comme il en avait reçu l’ordre afin de ne pas l’abîmer.

En 1923, un monument aux morts de la Grande Guerre, signé Jean-Georges Achard y est installé. 
En 1951, deux statues y sont déposées par l’Etat : Femme allongée de Marius Cladel et Nu de Louis Dejean. Aujourd’hui comme hier, le parc du palais Fénelon est propice aux promenades et aux rêveries.

Aujourd’hui encore, le parc recèle quelques magnifiques spécimens d’arbres remarquables : saules pleureurs, séquoias, hêtres pourpres…